package com.tgy.cmp;

import com.tgy.Sort;

/**
 * @Author: tgy
 * @Date: 2020-10-13 17:49
 */
public class HeapSort<E> extends Sort<E> {

    private int leaveSize;

    @Override
    protected void sort() {

        leaveSize = elements.length;
        heapify();

        while (true) {

            swap(0,leaveSize - 1);

            leaveSize--;

            if (leaveSize == 1) {

                break;
            }

            siftDown(0);
        }

    }

    private void heapify() {

        // 自下而上的下滤
        for (int i = (leaveSize >> 1) - 1; i >= 0; i--) {

            siftDown(i);
        }
    }

    private void siftDown(int index) {

        E e = elements[index];

        while (index < (leaveSize >> 1)) {

            int chiledIndex = (index << 1) + 1;

            // 如果右节点存在，则比较左右节点的大小
            if (chiledIndex + 1 < leaveSize) {

                if (compare(chiledIndex,chiledIndex + 1) < 0) {

                    chiledIndex = chiledIndex + 1;
                }
            }

            if (compare(e, elements[chiledIndex]) < 0) {

                elements[index] = elements[chiledIndex];
                index = chiledIndex;
            }else {

                break;
            }
        }

        elements[index] = e;
    }
}
